// class Solution {
// public:
//     vector<int> partitionLabels(string s) {
//         vector<int> v;
//         unordered_map<char, int> mp;
//         set<char> st;
//         for (const auto& e : s)
//             mp[e]++;
//         int j = -1;
//         for (int i = 0; i < s.size(); i++) {
//             st.insert(s[i]);
//             mp[s[i]]--;
//             bool vis = false;
//             for (const auto& e : st) {
//                 if (mp[e]) {
//                     vis = true;
//                     break;
//                 }
//             }
//             if (!vis) {
//                 v.push_back(i - j);
//                 j = i;
//                 st.clear();
//             }
//         }
//         return v;
//     }
// };

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> v;
        int last[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            last[s[i] - 'a'] = i;
        }
        int end = 0;
        int j = -1;
        for (int i = 0; i < s.size(); i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                v.push_back(i - j);
                j = i;
            }
        }
        return v;
    }
};